1. Field of the Invention
The present invention relates to a cryptographic method using elliptic curve, and more particularly, to an elliptic curve cryptographic method which is capable of preventing side channel attacks by applying an improved elliptic curve cryptographic algorithm using the encoding of a secret key.
2. Description of Related Art
Elliptic curve cryptosystem (ECC) was proposed by Victor Miller and Neal Koblitz in 1985. It is a public key cryptography scheme, and is getting increasing attention as the next generation cryptography technology for mobile environment.
The elliptic curve cryptography uses efficient algorithms, and 160 bit key, which is considerably smaller than the length requirement for the other public key cryptography schemes. Therefore, the elliptic curve cryptography system can be very effectively used in the smart card or wireless communication which has limited storage capacity and bandwidth. Wherever there is a conventional discrete logarithm-based public key cryptography applied, the elliptic curve cryptography can be compatibly applied.
The public key cryptography uses different keys for encryption and decryption, and according to this scheme, a sender receives its counterpart's public key, encrypts the received public key and sends it to the receiver, and the receiver decrypts the received data with its own secret key.
Private key information contains a pair of keys, that is, a public key and a secret key. Information such as individual's public key, elliptic curve information, and the resource and order of the elliptic curve cryptography groups are open information.
With the resource of the elliptic curve cryptography group “G” and the secret key “d”, the public key can be computed by an elliptic curve algorithm “E=[d]G”. “[d]G” is the sum of adding “G” by “d” times, which is the scalar multiplication.
“G” and “E” are points on the elliptic curve, and the elliptic curve represents the set of solutions (x, y) which satisfy the elliptic curve equation of the form on the finite field GF(pm):y2+a1xy+a2y=x3+a3x2+a4x+a5,where counts “a1” through “a5” belong to the finite field GF(pm), and the characteristic “p” is a fraction.
Although not existent in the equation, there is a point at infinity “0” in addition to the points (x, y), which serves as an identity element to the operations of the points on the curve. The points on the elliptic curve together with the point at infinity form a commutative group with respect to addition. The addition on the elliptic curve refers to the operation of two different points “P”, and the scalar multiplication refers to the operation of one point. Basically, the scalar multiplication is a doubling of a single point. Addition and doubling differs from each other in operation method thereof.
If characteristic “p” is not “2” or “3”, but a prime number, the elliptic curve equation may change to different form such as y2=x3+ax+b, where “a” and “b” are elements of the finite field “GF(p)” and 4a3+27b2≠0. If the characteristic “p” is “2”, the elliptic curve equation may change to a different form such as, y2+xy=3+ax2+b where “a” and “b” are elements of the finite field “GF(2n), and b≠0. The addition operation “P+Q=(x3, y3) and the doubling operation “2P=(x4, y4) of two points “P=(x1, y1)” and “Q=(x2, y2)” on the changed elliptic curve are computed by the following:
                                                                        x                3                            =                                                λ                  1                  2                                -                                  x                  1                                -                                  x                  2                                                                                                                                          y                  3                                =                                                                            λ                      1                                        ⁡                                          (                                                                        x                          1                                                -                                                  x                          3                                                                    )                                                        -                                      y                    1                                                              ,                                                λ                  1                                =                                                                            y                      2                                        -                                          y                      1                                                                                                  x                      2                                        -                                          x                      1                                                                                                                                                              x                4                            =                                                λ                  2                  2                                -                                  x                  1                                -                                  x                  2                                                                                                                                          y                  4                                =                                                                            λ                      1                                        ⁡                                          (                                                                        x                          1                                                -                                                  x                          4                                                                    )                                                        -                                      y                    1                                                              ,                                                λ                  2                                =                                                                            3                      ⁢                                              x                        1                        2                                                              +                    a                                                        2                    ⁢                                          y                      1                                                                                                                              [                  Formulae          ⁢                                          ⁢          1                ]            
As referred to by the above mathematical formulae, addition and doubling use different operations on the elliptic curve, and this fact can be utilized by the side channel attacks.
The ‘Side channel attack’ was introduced by Kocher in 1996. This addressed the problem of insecurity of secret key, in which the secret key is accessed even when the encryption algorithms are mathematically safe by using simple power analysis (SPA) or differential power analysis (DPA) which analyzes the time or power consumption for the operation of algorithms.
Accessing the secret key is not expected in the stage of executing the encryption algorithm, while inputs and encrypted outputs may be accessed. However, there is a leak of the secret key by the side channel attacks which utilize the fact that a certain number of encryption operations are performed using the secret key in the devices such as smart card, and thus the additional related information such as time and power consumption for the operation is obtainable.
A secret key for use in the execution of elliptic curve encryption algorithm is generated during the decoding process and electronic verification process. In decoding, a value “[d]P” is computed by the scalar multiplication of a point “P” on the elliptic curve and the private key “d”.
Considering that the scalar multiplication is performed with respect to the respective bits of the secret key “d” by addition and doubling, the respective bits of the secret key can be obtained by measuring the time or power consumption for the operations of the respective bits. This means that the secret key can be known based on the information such as time or power consumption for the operation.
SPA obtains information about the secret key, by measuring the power consumption for the encryption algorithm, and DPA collects the sampling data of the power consumption and analyzes the sampling data through digital signal interpretation and statistical methods.
Currently, a plurality of algorithms and devices are available to cope with the side channel attacks such as SPA and DPA. However, adding new devices to the hardware would bring in disadvantages such as increased requirement for capacity and power, which subsequently increases the volume and weight, and unit price of the encryption device.
Meanwhile, other types of algorithms are also available to cope with the side channel attacks, which include: an algorithm performing the same number of addition and doubling per unit; an algorithm using randomizer; and an algorithm using a modified finite operation which is the sub-operation of the scalar multiplication.
More specifically, the SPA obtains the secret information by utilizing the fact that only the doubling is performed when the private key's bit is zero ‘0’ and both the doubling and addition are performed when the bit is one ‘1.’ Therefore, the SPA obtains the secret information by measuring the power consumption and confirming whether the addition has been performed or not. The algorithm performing the same number of doubling and addition aims to prevent this information leakage by performing the addition even when the bit is zero ‘0.’
The result of the above-mentioned ‘dummy’ operation of the modified algorithm of the scalar multiplication may not be used after the completion of the operation. Alternatively, the Montgomery's algorithm, or a coding process of the private key, may be modified such that doubling and addition can be performed by equal times in every window.
However, the ‘dummy’ operation may not be safe if the attack utilizes the fact that the identity element is added when the most significant bit (MSB) is zero ‘0’ and the points on the elliptic curve are added when the MSB is one ‘1.’ The fact that the result of dummy operation is not used can also expose the system to the side channel attacks.
A Montgomery algorithm uses different points for operation, depending on whether the MSB is “0” or “1”, and therefore, it is not completely protected from the side channel attacks. Furthermore, the method of adopting new coding method for private key and iterating doubling and addition by identical number of times in every window, can only be used for the fixed window, and also requires twice the memory capacity than the window which does not consider SPA. Furthermore, because of the fact that the Montgomery algorithm uses identity element in the initial stage, it is also weak to the SPA.
The randomization usually comprises the operations of: projecting the points on the elliptic curve into randomly-selected similar-shaped curves; performing scalar multiplication with respect to the private key; and mapping the result of the scaler multiplication into the point on the elliptic curve. This method, however, usually has increase in operation load, and is weak to the DPA when applied with the window method. Additionally, the method is not applicable to all types of curves generally available, or not usable to the elliptic curve cryptography for certain types of finite field.
Another approach suggests to vary the finite field operation, which is sub-operation of the scalar multiplication. However, this approach has a degraded efficiency because of the requirement for different designs according to different operations of the addition and doubling in the computation in the finite field. Additionally, because this approach is applicable to certain limited types of curves, it is not generally applicable.